Theory Seminar

How to store a graph?

Speaker: Kshitij Gajjar, IIT Jodhpur
Time: 11:30AM, 6th June, 2023

Abstract

How does one store a graph in the database? Typically the vertices are labelled by a set {1, 2, …, n}. The edges can be denoted in many different ways: adjacency matrix, incidence matrix, adjacency list, to name a few. But what if the vertices are labelled in a more creative way, such that the labels of the vertices themselves denote their adjacencies? This eliminates the need for storing the edges! This topic is part of a heavily researched field called graph labelling, with connections to coding theory and information theory. In this talk, we will explore a type of graph labelling known as sum labelling. This is joint work with Henning Fernau https://eccc.weizmann.ac.il/report/2021/114.

Slides

© 2021 IIIT Hyderabad. All rights reserved.